package algorithm;

import java.util.LinkedList;
import java.util.Stack;

public class TreeTest {
    public static void main(String[] args) {
        TreeNode root = TreeUtil.buildTotalTree();
        // System.out.println(findK(root, 2));
        //System.out.println(getTreeHeight(root));
        //System.out.println(isBalanceTree(TreeUtil.buildSearchTree()));
        System.out.println(isTotalTree2(root));
    }

    public static int findK(TreeNode root,int k){
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        int i = 1;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                // 找到最左边
                TreeNode node = stack.pop();
                if (i++ == k) {
                    return node.data;
                }
                cur = node.right;
            }
        }
        return -1;
    }

    public static boolean isBalanceTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftHeight = getTreeHeight(root.left);
        int rightHeight = getTreeHeight(root.right);
        return Math.abs(leftHeight - rightHeight) <= 1;
    }

    // 获取二叉树的高度
    public static int getTreeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getTreeHeight(root.left);
        int rightHeight = getTreeHeight(root.right);
        return 1 + Math.max(rightHeight, leftHeight);
    }

    public static boolean isTotalTree(TreeNode root) {
        if (root == null) {
            return false;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                break;
            }else {
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        //判断队列中剩余的元素是否为空
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                return false;
            }
        }
        return true;
    }

    private static boolean isTotalTree2(TreeNode root) {
        if (root == null) {
            return true;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.pop();
            if (node != null) {
                queue.add(node.left);
                queue.add(node.right);
            } else {
                // 遇到空节点跳出循环
                break;
            }
        }
        // 队列中剩下的元素如果有非空节点，就不是完全二叉树
        for (TreeNode node : queue) {
            if (node != null) {
                return false;
            }
        }
        return true;
    }
}
